#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0
#define maxSize 100
#define vertex 5

typedef struct 
{
    char vexs[maxSize];  //顶点表
    int arcs[maxSize][maxSize];  //邻接矩阵
    int vexNum,arcNum;  // 图的点数、边数
}AMGraph;

typedef struct 
{
    int* base;  //动态分配的内存空间
    int tail;   // 尾指针
}SqQueue;

int Location(AMGraph* graph,char c)
{
    for(int i=0;i<graph->vexNum;i++)
    {
        if(graph->vexs[i]==c)
        {
            return i;
        }
    }
    return -1;
}

void creatUNM(AMGraph* graph,int countX)
{
    //countx 为节点的个数
    char buff[10];
    int count=0;
    FILE* f=fopen("./ax1.txt","r");
    
    while(fgets(buff,10,f)!=NULL)
    {
        count++;
    }
    fseek(f,0,SEEK_SET);
    graph->vexNum=countX;
    graph->arcNum=count-countX;

    for(int i=0;i<countX;i++)
    {
        fgets(buff,10,f);
        graph->vexs[i]=buff[0];  //载入顶点信息
    }
    for(int i=0;i<maxSize;i++)
    {
        for(int j=0;j<maxSize;j++)
        {
            graph->arcs[i][j]=0;  // 邻接矩阵初始化
        }
    }

    int v1,v2;   // 临时记录两个顶点的位置信息
    for(int i=0;i<(count-countX);i++)
    {
        fgets(buff,10,f);
        v1=Location(graph,buff[0]);
        v2=Location(graph,buff[2]);

        // 记录边的信息
        graph->arcs[v1][v2]=1;
        graph->arcs[v2][v1]=1; 
    }
    fclose(f);
}

// 深度优先遍历
void deepSearch(AMGraph* graph,int index,int* Visited)
{
    printf("%c\t",graph->vexs[index]);
    Visited[index]=1;

    for(int i=0;i<graph->vexNum;i++)
    {
        if((graph->arcs[index][i]!=0)&&(Visited[i]!=1))
        {
            deepSearch(graph,i,Visited);
        }
    }
}

// 队列的实现-->用于广度优先遍历

// 队列的初始化
SqQueue initQueue()
{
    int* basex=(int*) malloc(10*sizeof(int));
    SqQueue queue;
    queue.base=basex;
    for(int i=0;i<10;i++)
    {
        queue.base[i]=-1;
    }
    queue.tail=0;
    return queue;
}

// 队列的出队
int OutQueue(SqQueue* queue)
{
    int temp=-1;
    if(queue->base[0]!=-1)
    {
        temp=queue->base[0];
        for(int i=0;i<queue->tail-1;i++)
        {
            queue->base[i]=queue->base[i+1];
        }
        queue->tail--;
        queue->base[queue->tail]=-1;
    }
    return temp;
}

// 队列的入队
void joinQueue(SqQueue* queue,int data)
{
    queue->base[queue->tail++]=data;
}

//判断队列是否为空
int emptyQueue(SqQueue* queue)
{
    if(queue->tail==0)
    {
        return 1;
    }
    else
        return 0;
}

// 广度优先遍历
void spanSearch(AMGraph* graph,int index)
{
    printf("\n");
    int Visited[vertex]={0};
    int i;
    Visited[index]=1;
    SqQueue queue=initQueue();
    joinQueue(&queue,index);
    while(!emptyQueue(&queue))
    {
        index=OutQueue(&queue);
        printf("%c\t",graph->vexs[index]);
        for(i=0;i<graph->vexNum;i++)
        {
            if((graph->arcs[index][i]!=0)&&(Visited[i]!=1))
            {
                Visited[i]=1;
                // printf("%d\n",graph->vexs[index]);
                joinQueue(&queue,i);
            }
        }
    }
}

int countTuDegree(AMGraph* graph,int index)
{
    // 计算无向图中的度
    int sum=0;
    for(int i=0;i<vertex;i++)
    {
        if(graph->arcs[index][i]==1)
            sum++;
    }
    return sum;
}

void main()
{
    AMGraph graph;
    int visited[vertex]={0};
    creatUNM(&graph,vertex);
    deepSearch(&graph,1,visited);
    spanSearch(&graph,1);

    printf("\n图中a结点的度为%d\n",countTuDegree(&graph,0));
    printf("图中b结点的度为%d\n",countTuDegree(&graph,1));
}